package Classification;

import java.util.ArrayList;
import java.util.Dictionary;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.List;

import BasicMath.EuclideanDistance;

public class kNN {
	
	/**
	 * 
	 * @param k The number of neighbors to grab.
	 * @param CurrentObjectLocations An array with the location values of the object you wish to classify.
	 * @param OtherObjectLocations A two dimensional array with the objects in the first dimension and its location values in the second.
	 * @throws Exception 
	 * @returns the k nearest neighbors to the specified object.
	 */
	public static Dictionary<Integer, Double> NearestNeighbors(int k, Double[] CurrentObjectLocations, Double[][] OtherObjectLocations) throws Exception
	{
		if (k > OtherObjectLocations.length)
			throw new Exception("K cannot be greater than the number of objects");
		
		List<Double> distances = new ArrayList<Double>();
		
		Dictionary<Integer, Double> results = null;
		try 
		{
			for (int i = 0; i < OtherObjectLocations.length; i++)
				distances.add(EuclideanDistance.GetDistance(CurrentObjectLocations, OtherObjectLocations[i]));
		} catch (Exception e) {
			e.printStackTrace();
		}
		
		results = GetLowestKPairs(k, distances);
		
		return results;
	}
	
	public Dictionary<Integer, Double> GetKDistanceNeighborhood(int k, int ItemPosition, Double[][] DistanceMatrix)
	{
		Dictionary<Integer, Double> results = new Hashtable<Integer, Double>();
		
		Double kvalue = -1.0;
		kvalue = KDistance(k, ItemPosition, DistanceMatrix);
		
		//add any members that are the same as the kvalue
		for (int i = 0; i < DistanceMatrix[ItemPosition].length; i++)
		{
			if (i != ItemPosition)
			{
				if (DistanceMatrix[ItemPosition][i] <= kvalue)
				{
					if (results.get(i) == null)
						results.put(i, kvalue);
				}
			}
		}
		
		return results;
	}

	public static Double KDistance(int k, int ItemPosition,
			Double[][] DistanceMatrix) 
	{
		//Problem probably lies here
		Double[][] DistanceMatrixCopy = new Double[DistanceMatrix.length][DistanceMatrix.length];
		for (int i = 0; i < DistanceMatrix.length; i++)
			for (int j = 0; j < DistanceMatrix.length; j++)
				DistanceMatrixCopy[i][j] = DistanceMatrix[i][j];
		
		Dictionary<Integer, Double> results = new Hashtable<Integer, Double>();
		//calculate first k distances
		Double kvalue = -1.0;
		
		Integer minID;
		Double minDistance;
		for (int j = 0; j < k; j++)
		{
			minID = 0;
			minDistance = Double.MAX_VALUE;
			for (int i = 0; i < DistanceMatrixCopy[ItemPosition].length; i ++)
			{
				if (DistanceMatrixCopy[ItemPosition][i] != 0.0)
				{
					if (DistanceMatrixCopy[ItemPosition][i] < minDistance)
					{
						minID = i;
						minDistance = DistanceMatrixCopy[ItemPosition][i];
					}
				}
			}
			
			results.put(minID, minDistance);
			DistanceMatrixCopy[ItemPosition][minID] = 0.0;
		}
		
		//find the kvalue
		Enumeration<Integer> keys = results.keys();
		for (int i = 0; i < results.size(); i++)
		{
			Double value = results.get(keys.nextElement());
			if (value > kvalue)
				kvalue = value;
		}
		return kvalue;
	}
	
	private static Dictionary<Integer, Double> GetLowestKPairs(int k, List<Double> distances)
	{
		Dictionary<Integer, Double> results = new Hashtable<Integer, Double>();
		
		int minID;
		double minDistance;
		for (int i = 0; i < k; i++)
		{
			minID = 0;
			minDistance = distances.get(0);

			for (int j = 0; j < distances.size(); j++)
			{
				if (distances.get(j) < minDistance && distances.get(j) != 0.0)
				{
					minDistance = distances.get(j);
					minID = j;
				}
			}
			distances.set(minID, 0.0);
			results.put(minID, minDistance);
		}
		
		return results;
	}
}


